Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

In [16]:
import pdb
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # nums list length
        nums_len = len(nums)
        # sort nums
        nums.sort()
        
#         pdb.set_trace()
        delta = abs(target - nums[0] - nums[1] - nums[2])
        ans = 0
        for i in range(nums_len - 2):
            # 次级目标
            t_target = target - nums[i]
            j = i + 1
            k = nums_len - 1
            while j < k:
                tmp = t_target - nums[j]- nums[k]
                if tmp == 0:
                    return nums[i] + nums[j] + nums[k]
                if abs(tmp) <= delta:
                    delta = abs(tmp)
                    ans = nums[i] + nums[j] + nums[k]
#                     print(i, j, k, ans1, ans2, ans3)
                if tmp > 0 :
                    j += 1
                else:
                    k -= 1
                    
        return ans

In [17]:
Solution().threeSumClosest([-1,2, 1, -4], 1) # answer is 2


Out[17]:
2

In [18]:
Solution().threeSumClosest([0, 1, 2], 3)# answer 3 此处没通过是因为27行tmp<= delta,我写成delta<temp


Out[18]:
3

In [19]:
Solution().threeSumClosest([1,1,1,0], -100) # answer is 2 此处没有通过是因为忽略tmp和delta应该都是绝对值比较,不能只比较大小,abs(tmp)<= delta


Out[19]:
2

In [20]:
Solution().threeSumClosest([1,2,4,8,16,32,64,128], 82) # answer is 82 此处没有通过是因为tmp要知道left和right的走向 修改tmp>0 left += 1, or right -= 1


Out[20]:
82

In [22]:
Solution().threeSumClosest([1,1,-1,-1,3], -1) # answer is -1 ,搞不懂一模一样的代码,当前代码可以通过,自己重新打的一遍死活不过,对比了一下,没有发现哪里有所不同


Out[22]:
-1

In [ ]: